package com.heima.algorithm.sort;

/**
 * <strong>归并插入排序</strong>
 * <p>大规模数据用归并排序效率好，小规模、有序度高用插入排序效果更好</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/30 23:45
 */
public class MergeInsertionSort {
    //（1）小规模、有序度高用插入排序效果更好
    //（2）大规模数据用归并排序效果更好

    private static final int INSERTION_SORT_THRESHOLD = 32; // 插入排序的临界值

    /**
     * 归并插入排序
     * @param arr 待排序的数组
     */
    public static void mergeInsertionSort(int[] arr) {
        int[] result = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, result);
    }

    /**
     * 递归调用，将数组分为左右两个子数组，分别排序，再合并，覆盖当前范围内的原数组，覆盖的原因是需要保证左右数组的有序性
     * @param arr 数组
     * @param begin 开始索引
     * @param end 结束索引
     * @param result 临时数组，存放合并后的结果
     */
    private static void mergeSort(int[] arr, int begin, int end, int[] result){
        // 递归结束条件：当前数组范围区间内最多只有32个元素，那么进行插入排序
        if (end - begin <= INSERTION_SORT_THRESHOLD){
            insertionSort(arr, begin, end);
            return;
        }
        // 递的时候将数组一分为二
        // 这里用无符号右移是因为begin + end有可能越界，变为负数，直接用除法性能低而且失真，用有符号一位运算，变负数后左边会补1，会失真
        int median = (begin + end) >>> 1;
        // 这里用median是因为请看：0 1 2 3 4 5 6 7  0 1 2 3 4 5 6 7 8
        mergeSort(arr, begin, median, result);
        mergeSort(arr, median + 1, end, result);
        // 归的时候合并两个数组
        merge(arr, begin, median, end, result);
        // 将合并的结果覆盖指定范围内的原数组
        System.arraycopy(result, begin, arr, begin, end - begin + 1);
    }

    /**
     * 拷贝左右两个有序数组，合并成一个新的有序数组
     * @param arr 数组
     * @param begin 左数组的第一个元素
     * @param median 左数组的最后一个元素，也是右数组的第一个元素的前一个元素
     * @param end  右数组的最后一个元素
     * @param result 存放合并后的结果的数组
     */
    private static void merge(int[] arr, int begin, int median, int end, int[] result) {
        // 指针p1指向左边数组的首元素
        int p1 = begin;
        // 指针p2指向右边数组的首元素
        int p2 = median + 1;
        // 指针start指向合并后的数组的起始位置
        int start = begin;
        // 只要p1或者p2有一个没有移动到边界，就继续循环
        while (p1 <= median || p2 <= end){
            // 两者都还有元素
            if (p1 <= median && p2 <= end){
                // 比较两个元素，将较小的元素放入合并后的数组中
                if (arr[p1] <= arr[p2]){
                    result[start++] = arr[p1++];
                }else {
                    result[start++] = arr[p2++];
                }
            }
            // 左边还有元素，但是右边已经处理完了
            else if (p1 <= median) {
                System.arraycopy(arr, p1, result, start, median - p1 + 1);
                return;
            }
            // 右边还有元素，但是左边已经处理完了
            else {
                System.arraycopy(arr, p2, result, start, end - p2 + 1);
                return;
            }
        }
    }

    /**
     * 指定范围内进行插入排序
     * @param arr 数组
     * @param begin 指定范围内第一个元素
     * @param end 指定范围内最后一个元素
     */
    private static void insertionSort(int[] arr, int begin, int end){
        for (int i = begin + 1; i <= end; i++){
            int inserted = arr[i];
            int index = i;
            // 找到插入的位置
            while (index > begin && arr[index - 1] > inserted){
                arr[index] = arr[index - 1];
                index--;
            }
            // 插入
            if (index != i){
                arr[index] = inserted;
            }
        }
    }
}
